#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> vv;
        vv.resize(0);
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int a = 0; a < n - 3;)
        {
            if (nums[a] > 0 && nums[a] >= target)
                break;
            for (int b = a + 1; b < n - 2;)
            {
                if (nums[a] > 0 && (long long)nums[b] >= (long long)target - nums[a])
                    break;
                int left = b + 1;
                int right = n - 1;
                while (left < right)
                {
                    if ((long long)nums[left] + nums[right] < (long long)target - nums[a] - nums[b])
                        left++;
                    else if ((long long)nums[left] + nums[right] > (long long)target - nums[a] - nums[b])
                        right--;
                    else
                    {
                        vv.push_back({ nums[a], nums[b], nums[left], nums[right] });
                        int x = nums[left], y = nums[right];
                        left++;
                        right--;
                        while (left < right)
                        {
                            if (x != nums[left])
                                break;
                            else
                                left++;
                        }
                        while (left < right)
                        {
                            if (y != nums[right])
                                break;
                            else
                                right--;
                        }
                    }
                }
                int z = nums[b++];
                while (b < n - 2)
                {
                    if (z != nums[b])
                        break;
                    else
                        b++;
                }
            }
            int q = nums[a++];
            while (a < n - 3)
            {
                if (q != nums[a])
                    break;
                else
                    a++;
            }
        }
        return vv;
    }
};